{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# FP-growth算法来高效发现频繁项集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FP树：用于编码数据集的有效方式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。\n",
    "\n",
    "FP代表频繁模式（Frequent Pattern）。\n",
    "\n",
    "一棵FP树看上去与计算机科学中的其他树结构类似，但是它通过链接（link）来连接相似元素，被连起来的元素项可以看成一个链表。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "与搜索树不同的是，一个元素项可以在一棵FP树种出现多次。\n",
    "\n",
    "FP树会存储项集的出现频率，而每个项集会以路径的方式存储在数中。 \n",
    "\n",
    "树节点上给出集合中的单个元素及其在序列中的出现次数，路径会给出该序列的出现次数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "相似项之间的链接称为节点链接（node link），用于快速发现相似项的位置。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**下图给出了FP树的一个例子**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "事务集\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| 事务ID        | 事务中的元素项   | \n",
    "| --------   | -----  | \n",
    "|001\t|r, z, h, j, p|\n",
    "|002|\tz, y, x, w, v, u, t, s|\n",
    "|003\t|z|\n",
    "|004|\tr, x, n, o, s|\n",
    "|005\t|y, r, x, z, q, t, p|\n",
    "|006\t|y, z, x, e, q, s, t, m|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "生成的FP树为\n",
    "```\n",
    "\n",
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/fa5f320274c7d97ea51142743aceb287.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**对FP树的解读：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "图中，元素项z出现了5次，集合{r, z}出现了1次。\n",
    "\n",
    "于是可以得出结论：z一定是自己本身或者和其他符号一起出现了4次。\n",
    "\n",
    "集合{t, s, y, x, z}出现了2次，集合{t, r, y, x, z}出现了1次，z本身单独出现1次。\n",
    "\n",
    "就像这样，FP树的解读方式是读取某个节点开始到根节点的路径。\n",
    "\n",
    "路径上的元素构成一个频繁项集，开始节点的值表示这个项集的支持度。\n",
    "\n",
    "根据图，我们可以快速读出项集{z}的支持度为5、项集{t, s, y, x, z}的支持度为2、项集{r, y, x, z}的支持度为1、项集{r, s, x}的支持度为1。\n",
    "\n",
    "FP树中会多次出现相同的元素项，也是因为同一个元素项会存在于多条路径，构成多个频繁项集。\n",
    "\n",
    "但是频繁项集的共享路径是会合并的，如图中的{t, s, y, x, z}和{t, r, y, x, z}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "和之前一样，我们取一个最小阈值，出现次数低于最小阈值的元素项将被直接忽略。图中将最小支持度设为3，所以q和p没有在FP中出现。\n",
    "\n",
    "**FP-growth算法的工作流程如下:**\n",
    "\n",
    "首先构建FP树，然后利用它来挖掘频繁项集。\n",
    "\n",
    "为构建FP树，需要对原始数据集扫描两遍。\n",
    "\n",
    "第一遍对所有元素项的出现次数进行计数。\n",
    "\n",
    "数据库的第一遍扫描用来统计出现的频率，而第二遍扫描中只考虑那些频繁元素。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**FP-growth算法发现频繁项集的基本过程如下：**\n",
    "\n",
    " - 构建FP树 \n",
    " - 从FP树中挖掘频繁项集 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**头指针表**\n",
    "\n",
    "FP-growth算法还需要一个称为头指针表的数据结构，其实很简单，就是用来记录各个元素项的总出现次数的数组，再附带一个指针指向FP树中该元素项的第一个节点。这样每个元素项都构成一条单链表。\n",
    "\n",
    "图示说明：\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/2628b6024f09d414cb430b692028facd.png)\n",
    "\n",
    "这里使用Python字典作为数据结构，来保存头指针表。以元素项名称为键，保存出现的总次数和一个指向第一个相似元素项的指针。\n",
    "\n",
    "第一次遍历数据集会获得每个元素项的出现频率，去掉不满足最小支持度的元素项，生成这个头指针表。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**元素项排序**\n",
    "\n",
    "上文提到过，FP树会合并相同的频繁项集（或相同的部分）。\n",
    "\n",
    "因此为判断两个项集的相似程度需要对项集中的元素进行排序（不过原因也不仅如此，还有其它好处）。\n",
    "\n",
    "排序基于元素项的绝对出现频率（总的出现次数）来进行。\n",
    "\n",
    "在第二次遍历数据集时，会读入每个项集（读取），去掉不满足最小支持度的元素项（过滤），然后对元素进行排序（重排序）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**构建FP树**\n",
    "\n",
    "在对事务记录过滤和排序之后，就可以构建FP树了。\n",
    "\n",
    "从空集开始，将过滤和重排序后的频繁项集一次添加到树中。如果树中已存在现有元素，则增加现有元素的值；如果现有元素不存在，则向树添加一个分支。\n",
    "\n",
    "对前两条事务进行添加的过程：\n",
    "\n",
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/ccee345cca3b9e9130fec721d71681cf.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**实现流程**\n",
    "\n",
    "输入：数据集、最小值尺度\n",
    "输出：FP树、头指针表\n",
    "\n",
    " - 1、遍历数据集，统计各元素项出现次数，创建头指针表\n",
    " - 2、移除头指针表中不满足最小值尺度的元素项\n",
    " - 3、第二次遍历数据集，创建FP树。对每个数据集中的项集：\n",
    "  - 3.1 初始化空FP树\n",
    "  - 3.2 对每个项集进行过滤和重排序\n",
    "  - 3.3 使用这个项集更新FP树，从FP树的根节点开始：\n",
    "     - 3.3.1 如果当前项集的第一个元素项存在于FP树当前节点的子节点中，则更新这个子节点的计数值\n",
    "     - 3.3.2 否则，创建新的子节点，更新头指针表\n",
    "     - 3.3.3 对当前项集的其余元素项和当前元素项的对应子节点递归3.3的过程\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**从一棵FP树种挖掘频繁项集**\n",
    "\n",
    "从FP树中抽取频繁项集的三个基本步骤如下：\n",
    "\n",
    " - 从FP树中获得条件模式基； \n",
    " - 利用条件模式基，构建一个条件FP树； \n",
    " - 迭代重复步骤1步骤2，直到树包含一个元素项为止。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "其中“条件模式基”是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径（prefix path）。\n",
    "\n",
    "简而言之，一条前缀路径是介于所查找元素项与树根节点之间的所有内容。\n",
    "\n",
    "例如\n",
    "\n",
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/0d239b4d7b15973a7612b0d1d71ba36b.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "则每一个频繁元素项的条件模式基为：\n",
    "\n",
    "| 频繁项  |  前缀路径 |\n",
    "| ----| ----|\n",
    "|z|\t{}: 5|\n",
    "|r|{x, s}: 1, {z, x, y}: 1, {z}: 1|\n",
    "|x|\t{z}: 3, {}: 1|\n",
    "|y|\t{z, x}: 3|\n",
    "|s|\t{z, x, y}: 2, {x}: 1|\n",
    "|t|\t{z, x, y, s}: 2, {z, x, y, r}: 1|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "发现规律了吗，z存在于路径{z}中，因此前缀路径为空，另添加一项该路径中z节点的计数值5构成其条件模式基；\n",
    "\n",
    "r存在于路径{r, z}、{r, y, x, z}、{r, s, x}中，分别获得前缀路径{z}、{y, x, z}、{s, x}，另添加对应路径中r节点的计数值（均为1）构成r的条件模式基；\n",
    "\n",
    "以此类推。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**创建条件FP树**\n",
    "\n",
    "对于每一个频繁项，都要创建一棵条件FP树。可以使用刚才发现的条件模式基作为输入数据，并通过相同的建树代码来构建这些树。\n",
    "\n",
    "例如\n",
    "\n",
    ">对于r，即以“{x, s}: 1, {z, x, y}: 1, {z}: 1”为输入，调用函数createTree()获得r的条件FP树；\n",
    "\n",
    ">对于t，输入是对应的条件模式基“{z, x, y, s}: 2, {z, x, y, r}: 1”。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**递归查找频繁项集**\n",
    " \n",
    "有了FP树和条件FP树，我们就可以在前两步的基础上递归得查找频繁项集。\n",
    "\n",
    "递归的过程是这样的：\n",
    "输入：我们有当前数据集的FP树（inTree，headerTable）\n",
    "\n",
    " - 1、初始化一个空列表preFix表示前缀\n",
    " - 2、初始化一个空列表freqItemList接收生成的频繁项集（作为输出）\n",
    " - 3、对headerTable中的每个元素basePat（按计数值由小到大），递归：\n",
    "  - 3.1 记basePat + preFix为当前频繁项集newFreqSet\n",
    "  - 3.2 将newFreqSet添加到freqItemList中\n",
    "  - 3.3 计算t的条件FP树（myCondTree、myHead）\n",
    "  - 3.4 当条件FP树不为空时，继续下一步；否则退出递归\n",
    "  - 3.5 以myCondTree、myHead为新的输入，以newFreqSet为新的preFix，外加freqItemList，递归这个过程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**实现代码**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# FP树类\n",
    "class treeNode:\n",
    "    def __init__(self, nameValue, numOccur, parentNode):\n",
    "        self.name = nameValue  #节点元素名称，在构造时初始化为给定值\n",
    "        self.count = numOccur   # 出现次数，在构造时初始化为给定值\n",
    "        self.nodeLink = None   # 指向下一个相似节点的指针，默认为None\n",
    "        self.parent = parentNode   # 指向父节点的指针，在构造时初始化为给定值\n",
    "        self.children = {}  # 指向子节点的字典，以子节点的元素名称为键，指向子节点的指针为值，初始化为空字典\n",
    "\n",
    "    # 增加节点的出现次数值\n",
    "    def inc(self, numOccur):\n",
    "        self.count += numOccur\n",
    "\n",
    "    # 输出节点和子节点的FP树结构\n",
    "    def disp(self, ind=1):\n",
    "        print(' ' * ind, self.name, ' ', self.count)\n",
    "        for child in self.children.values():\n",
    "            child.disp(ind + 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# =======================================================构建FP树==================================================\n",
    "\n",
    "\n",
    "# 对不是第一个出现的节点，更新头指针块。就是添加到相似元素链表的尾部\n",
    "def updateHeader(nodeToTest, targetNode):\n",
    "    while (nodeToTest.nodeLink != None):\n",
    "        nodeToTest = nodeToTest.nodeLink\n",
    "    nodeToTest.nodeLink = targetNode\n",
    "\n",
    "# 根据一个排序过滤后的频繁项更新FP树\n",
    "def updateTree(items, inTree, headerTable, count):\n",
    "    if items[0] in inTree.children:\n",
    "        # 有该元素项时计数值+1\n",
    "        inTree.children[items[0]].inc(count)\n",
    "    else:\n",
    "        # 没有这个元素项时创建一个新节点\n",
    "        inTree.children[items[0]] = treeNode(items[0], count, inTree)\n",
    "        # 更新头指针表或前一个相似元素项节点的指针指向新节点\n",
    "        if headerTable[items[0]][1] == None:  # 如果是第一次出现，则在头指针表中增加对该节点的指向\n",
    "            headerTable[items[0]][1] = inTree.children[items[0]]\n",
    "        else:\n",
    "            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])\n",
    "\n",
    "    if len(items) > 1:\n",
    "        # 对剩下的元素项迭代调用updateTree函数\n",
    "        updateTree(items[1::], inTree.children[items[0]], headerTable, count)\n",
    "\n",
    "\n",
    "\n",
    "# 主程序。创建FP树。dataSet为事务集，为一个字典，键为每个事物，值为该事物出现的次数。minSup为最低支持度\n",
    "def createTree(dataSet, minSup=1):\n",
    "    # 第一次遍历数据集，创建头指针表\n",
    "    headerTable = {}\n",
    "    for trans in dataSet:\n",
    "        for item in trans:\n",
    "            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]\n",
    "    # 移除不满足最小支持度的元素项\n",
    "    keys = list(headerTable.keys()) # 因为字典要求在迭代中不能修改，所以转化为列表\n",
    "    for k in keys:\n",
    "        if headerTable[k] < minSup:\n",
    "            del(headerTable[k])\n",
    "    # 空元素集，返回空\n",
    "    freqItemSet = set(headerTable.keys())\n",
    "    if len(freqItemSet) == 0:\n",
    "        return None, None\n",
    "    # 增加一个数据项，用于存放指向相似元素项指针\n",
    "    for k in headerTable:\n",
    "        headerTable[k] = [headerTable[k], None]  # 每个键的值，第一个为个数，第二个为下一个节点的位置\n",
    "    retTree = treeNode('Null Set', 1, None) # 根节点\n",
    "    # 第二次遍历数据集，创建FP树\n",
    "    for tranSet, count in dataSet.items():\n",
    "        localD = {} # 记录频繁1项集的全局频率，用于排序\n",
    "        for item in tranSet:\n",
    "            if item in freqItemSet:   # 只考虑频繁项\n",
    "                localD[item] = headerTable[item][0] # 注意这个[0]，因为之前加过一个数据项\n",
    "        if len(localD) > 0:\n",
    "            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] # 排序\n",
    "            updateTree(orderedItems, retTree, headerTable, count) # 更新FP树\n",
    "    return retTree, headerTable\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# =================================================查找元素条件模式基===============================================\n",
    "\n",
    "# 直接修改prefixPath的值，将当前节点leafNode添加到prefixPath的末尾，然后递归添加其父节点。\n",
    "# prefixPath就是一条从treeNode（包括treeNode）到根节点（不包括根节点）的路径\n",
    "def ascendTree(leafNode, prefixPath):\n",
    "    if leafNode.parent != None:\n",
    "        prefixPath.append(leafNode.name)\n",
    "        ascendTree(leafNode.parent, prefixPath)\n",
    "\n",
    "# 为给定元素项生成一个条件模式基（前缀路径）。basePet表示输入的频繁项，treeNode为当前FP树中对应的第一个节点\n",
    "# 函数返回值即为条件模式基condPats，用一个字典表示，键为前缀路径，值为计数值。\n",
    "def findPrefixPath(basePat, treeNode):\n",
    "    condPats = {}  # 存储条件模式基\n",
    "    while treeNode != None:\n",
    "        prefixPath = []  # 用于存储前缀路径\n",
    "        ascendTree(treeNode, prefixPath)  # 生成前缀路径\n",
    "        if len(prefixPath) > 1:\n",
    "            condPats[frozenset(prefixPath[1:])] = treeNode.count  # 出现的数量就是当前叶子节点的数量\n",
    "        treeNode = treeNode.nodeLink  # 遍历下一个相同元素\n",
    "    return condPats\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# =================================================递归查找频繁项集===============================================\n",
    "# 根据事务集获取FP树和频繁项。\n",
    "# 遍历频繁项，生成每个频繁项的条件FP树和条件FP树的频繁项\n",
    "# 这样每个频繁项与他条件FP树的频繁项都构成了频繁项集\n",
    "\n",
    "# inTree和headerTable是由createTree()函数生成的事务集的FP树。\n",
    "# minSup表示最小支持度。\n",
    "# preFix请传入一个空集合（set([])），将在函数中用于保存当前前缀。\n",
    "# freqItemList请传入一个空列表（[]），将用来储存生成的频繁项集。\n",
    "def mineTree(inTree, headerTable, minSup, preFix, freqItemList):\n",
    "    # 对频繁项按出现的数量进行排序进行排序\n",
    "    sorted_headerTable = sorted(headerTable.items(), key=lambda p: p[1][0])  #返回重新排序的列表。每个元素是一个元组，[（key,[num,treeNode],()）\n",
    "    bigL = [v[0] for v in sorted_headerTable]  # 获取频繁项\n",
    "    for basePat in bigL:\n",
    "        newFreqSet = preFix.copy()  # 新的频繁项集\n",
    "        newFreqSet.add(basePat)     # 当前前缀添加一个新元素\n",
    "        freqItemList.append(newFreqSet)  # 所有的频繁项集列表\n",
    "        condPattBases = findPrefixPath(basePat, headerTable[basePat][1])  # 获取条件模式基。就是basePat元素的所有前缀路径。它像一个新的事务集\n",
    "        myCondTree, myHead = createTree(condPattBases, minSup)  # 创建条件FP树\n",
    "\n",
    "        if myHead != None:\n",
    "            # 用于测试\n",
    "            print('conditional tree for:', newFreqSet)\n",
    "            myCondTree.disp()\n",
    "            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)  # 递归直到不再有元素\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 生成数据集\n",
    "def loadSimpDat():\n",
    "    simpDat = [['r', 'z', 'h', 'j', 'p'],\n",
    "               ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],\n",
    "               ['z'],\n",
    "               ['r', 'x', 'n', 'o', 's'],\n",
    "               ['y', 'r', 'x', 'z', 'q', 't', 'p'],\n",
    "               ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]\n",
    "    return simpDat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 将数据集转化为目标格式\n",
    "def createInitSet(dataSet):\n",
    "    retDict = {}\n",
    "    for trans in dataSet:\n",
    "        retDict[frozenset(trans)] = 1\n",
    "    return retDict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "conditional tree for: {'y'}\n",
      "  Null Set   1\n",
      "   z   3\n",
      "    x   3\n",
      "conditional tree for: {'y', 'x'}\n",
      "  Null Set   1\n",
      "   z   3\n",
      "conditional tree for: {'s'}\n",
      "  Null Set   1\n",
      "   x   3\n",
      "conditional tree for: {'t'}\n",
      "  Null Set   1\n",
      "   z   3\n",
      "    y   3\n",
      "     x   3\n",
      "conditional tree for: {'y', 't'}\n",
      "  Null Set   1\n",
      "   z   3\n",
      "conditional tree for: {'x', 't'}\n",
      "  Null Set   1\n",
      "   z   3\n",
      "    y   3\n",
      "conditional tree for: {'x', 'y', 't'}\n",
      "  Null Set   1\n",
      "   z   3\n",
      "conditional tree for: {'x'}\n",
      "  Null Set   1\n",
      "   z   3\n",
      "[{'r'}, {'y'}, {'z', 'y'}, {'y', 'x'}, {'z', 'y', 'x'}, {'s'}, {'s', 'x'}, {'t'}, {'z', 't'}, {'y', 't'}, {'z', 'y', 't'}, {'x', 't'}, {'z', 'x', 't'}, {'x', 'y', 't'}, {'z', 'x', 'y', 't'}, {'x'}, {'z', 'x'}, {'z'}]\n"
     ]
    }
   ],
   "source": [
    "minSup =3\n",
    "simpDat = loadSimpDat()  # 加载数据集\n",
    "initSet = createInitSet(simpDat)  # 转化为符合格式的事务集\n",
    "myFPtree, myHeaderTab = createTree(initSet, minSup)  # 形成FP树\n",
    "# myFPtree.disp()  # 打印树\n",
    "\n",
    "freqItems = []  # 用于存储频繁项集\n",
    "mineTree(myFPtree, myHeaderTab, minSup, set([]), freqItems)  # 获取频繁项集\n",
    "print(freqItems)  # 打印频繁项集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**FP-growth算法总结**\n",
    "\n",
    "FP-growth算法是一种用于发现数据集中频繁模式的有效方法。\n",
    "\n",
    "FP-growth算法利用Apriori原则，执行更快。Apriori算法产生候选项集，然后扫描数据集来检查它们是否频繁。\n",
    "\n",
    "由于只对数据集扫描两次，因此FP-growth算法执行更快。\n",
    "\n",
    "在FP-growth算法中，数据集存储在一个称为FP树的结构中。\n",
    "\n",
    "FP树构建完成后，可以通过查找元素项的条件基及构建条件FP树来发现频繁项集。\n",
    "\n",
    "该过程不断以更多元素作为条件重复进行，直到FP树只包含一个元素为止。\n",
    "\n",
    "优缺点：\n",
    "\n",
    " - 优点：一般要快于Apriori。 \n",
    " - 缺点：实现比较困难，在某些数据集上性能会下降。 \n",
    " - 适用数据类型：离散型数据。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
